Dynamic management of memory, that is dynamic allocation and deallocation of memory to executing programs, regardless of whether it is implemented in a memory controller, an operating system, or a runtime library of a programming language, allows more efficient utilization of the available memory pool. Traditionally, a memory pool is dynamically managed using one of five well known classical methods; namely, First Fit, Best Fit, Buddy, Left Most and Better Fit. Each of the classical dynamic memory management methods has its advantages and disadvantages. Preferences typically depend on trade-offs between performance versus memory utilization.
Under the First Fit and Best Fit methods, performance is traded off for fuller memory utilization. The small typically useless memory fragments resulting from repeated allocations and deallocations are still tracked and chained in the free memory list at the expense of increased allocation time. In contrast, the Buddy method trades off memory utilization for performance. By rounding memory request up to an allowable size, the Buddy method eliminates these small useless memory fragments and therefore the time wasted on chaining them in the free memory list at the expense of wasted memory. Typically, the Buddy method requires a larger amount of space than a similarly-sized memory request using the First Fit or Best Fit methods.
Similarly, the Left Most Fit method trades memory utilization for performance. By allocating only from the left side of the free memory tree, the Left Most Fit method improves allocation time at the expense of an unbalanced free memory tree with small useless memory fragments accumulated on the right hand side of the free memory tree. Likewise, the Better Fit method trades performance for memory utilization. By allocating from both sides of the free memory tree and preserving the larger memory fragments, the Better Fit method reduces the small useless memory fragments at the expense of allocation time.
One disadvantage of the five classical methods is that they are not optimized to take advantage of virtual address systems using physical memory space including both host memory and local graphics memory. With the development of the Accelerated Graphics Port (AGP) interface specification, the ability to use this virtual memory space for graphics rendering has become possible.
The AGP interface may work with the peripheral component interconnect (PCI) bus specification in order to provide users with high-speed graphics computer platforms. More information about virtual memory AGP and PCI systems can be found in the current AGP Interface Specification, Rev. 1.0 (July 1996), available from Intel Corporation of Santa Clara, Calif. The PCI protocol is described in the current PCI Local Bus Specification, Rev. 2.1 (July 1995), available from the PCI Special Interest Group (SIG) in Hillsboro, Ore.
The AGP interface may operate in either a direct memory access (DMA) mode, wherein data is transferred from system memory to local memory before execution, or an execute mode wherein a combination of local memory and system memory are used as primary graphics memory. The execute mode is advantageous in that either local or system memory space may be used according to performance optimization routines. When the AGP interface is running in execute mode, it is imperative that a memory mapping mechanism be used to map random pages of memory into a contiguous physical address space.
One aspect of the PCI and AGP system is that it provides for an area of PCI memory reserved for the graphics linear frame buffer. This memory area is referred to as the "Linear Frame Buffer Aperture." This space is reserved upon boot-up specifically to hold the frame buffer.
It is desirable to implement a dynamic memory management method that is portable to a virtual memory system, wherein the physical memory includes both local graphics memory and system memory segments. As will be disclosed, the present invention provides a method and apparatus for dynamic memory management that achieves the desirable result.